import java.util.ArrayList;
/**
 * 描述：基于二分搜索树的Map
 *
 * @author 王博
 * @version 1.0
 * create 2018-10-23-23:28
 */
public class BSTMap <K  extends Comparable<K>,V>implements Map<K,V> {


    private class Node{
        public K key;
        public V value;
        public Node left,right;

        public Node(K key,V value){
            this.key = key;
            this.value = value;
            left = null;
            right = null;
        }

        public Node(K key){
            this.key = key;
            this.value = null;
            left = null;
            right = null;
        }
    }

    private Node root;
    private int size;

    public BSTMap(){
        root = null;
        size = 0 ;

    }

    @Override
    public boolean isEmpty( ) {
        return size == 0;
    }

    @Override
    public int getSize( ) {
        return size;
    }

    @Override
    public void add(K key , V value) {
        root = add( root ,key,value);
    }

    /**
     *
     * @param node 当前节点
     * @param key 需要插入的key
     * @param value 需要插入的value
     * @return 返回当前节点
     */
    private Node add(Node node,K key ,V value){

        if(node == null){
            size++;
            return new Node(key,value);
        }
        if(key.compareTo (node.key)<0){
            node.left = add(node.left,key,value);
        }else if(key.compareTo (node.key) > 0)
            node.right = add(node.right,key,value);
        else
            //处理相等的情况
            node.value = value;
        return node;
    }

    /**
     *
     * @param node 根节点
     * @param key 所查询的Key
     * @return 以node为根节点bst中，key所在的节点
     */
    private Node getNode(Node node,K key){
        if(node == null)
            return null;

        if(key.compareTo (node.key)==0)
            return node;//找到了
        else if(key.compareTo (node.key)<0)
            return getNode (node.left,key);//去左子树找
        else
            return getNode (node.right,key);//去右子树找
    }

    @Override
    public boolean contains(K key) {

        return getNode (root,key)!=null;
    }

    @Override
    public V get(K key) {
        Node node = getNode (root,key);

        return node == null?null:node.value;
    }

    @Override
    public void set(K key , V newValue) {
        Node node = getNode (root,key);
        if(node == null){
            //这是因为我已经确定用户知道这里有值，但是没有，所以抛异常
            throw new IllegalArgumentException ("key is not exsit");
        }else
            node.value = newValue;
    }

    @Override
    public V remove(K key) {
        return remove (root,key).value;
    }

    private Node remove(Node node,K key){
        if(node == null)
            return null;

        if(key.compareTo (node.key) < 0)
        {
            node.left= remove (node.left,key);
            return node;

        }else if(key.compareTo (node.key)>0){
            node.right= remove (node.right,key);
            return node;
        }else{
            if(node.left == null){

                Node rightNode = node.right;
                node.right = null;
                size --;
                return rightNode;
            }

            if(node.right == null){

                Node leftNode = node.left;
                node.left = null;
                size --;
                return leftNode;
            }

            Node successor = minimum (node.right);
            successor.right = removeMin (node.right);
            successor.left = node.left;

            node.left = node.right = null;

            return successor;

        }

    }



    /**
     * 获得最小值的递归部分
     * @param node
     * @return
     */
    private Node minimum(Node node){
        if(node.left == null)
            return node;
        else
            return minimum (node.left);

    }

    /**
     * 删除掉以node为节点的二分搜索数的最小节点
     * 并返回删除节点后的新的二分搜索数的根
     * @param node
     * @return
     */
    private Node removeMin(Node node){
        if(node.left == null){
            Node rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;
        }

        node.left = removeMin (node.left);
        return node;
    }

    public static void main(String[] args){
        BSTMap<String,Integer>  map= new BSTMap<> ();

        map.add ("cnm",1);
        System.out.println (map.getSize ());
        ArrayList<Integer> list = new ArrayList <> ();

    }
}
